package day_2022_7_to_8.day48;

import java.util.HashMap;
import java.util.Map;



/**
 * @author haomin
 * @date 2022/09/01 23:34
 **/
public class Day47_4_Offer35_CopyRandomList {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    class Solution {
        public Node copyRandomList(Node head) {
            if(head == null) return null;

            Map<Node, Node> map = new HashMap<>();
            for(Node x = head; x != null; x = x.next){
                Node newNode = new Node(x.val);
                map.put(x, newNode);
            }
            for(Node x = head; x != null; x = x.next){
                map.get(x).next = map.get(x.next);
                map.get(x).random = map.get(x.random);
            }
            return map.get(head);
        }
    }
    class Solution2 {
        public Node copyRandomList(Node head) {
            if(head == null) return null;
            for(Node node = head, newNode = null; node != null; node = node.next.next){
                newNode = new Node(node.val);
                newNode.next = node.next;
                node.next = newNode;
            }
            for(Node node = head; node != null; node = node.next.next){
                if(node.random != null){
                    node.next.random = node.random.next;
                }
            }
            Node second = head.next;
            for(Node node = head , next = null; node != null && node.next != null;){
                next = node.next;
                node.next = next.next;
                node = next;
            }
            return second;
        }
    }
}